import java.util.*;

class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}


class TreeNode {
   int val = 0;
   TreeNode left = null;
   TreeNode right = null;
   public TreeNode(int val) {
     this.val = val;
   }
 }


public class Test {
    /*
    题目1 ：合并两个有序链表
     */
    //方法一： 递归
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null){
            return list2;
        }else if(list2 == null){
            return list1;
        }else if(list1.val < list2.val){
            list1.next = Merge(list1.next, list2);
            return list1;
        }else{
            list2.next = Merge(list1, list2.next);
            return list2;
        }
    }

    //方法2 ：迭代
    public ListNode Merge1(ListNode list1,ListNode list2) {
        ListNode head = new ListNode(-10);
        //怎么设置头部？
        //哑节点
        ListNode cur = head;

        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                cur.next = list1;
                cur = list1;
                list1 = list1.next;
            }else{
                cur.next = list2;
                cur = list2;
                list2 = list2.next;
            }
        }

        if(list1 != null){
            cur.next = list1;
        }

        if(list2 != null){
            cur.next = list2;
        }

        return head.next;
    }

    /*
    题目 3：二叉树的镜像
     */
    public TreeNode Mirror (TreeNode pRoot) {
        if(pRoot == null){
            return pRoot;
        }

        //递归左子树
        TreeNode left = Mirror(pRoot.left);
        TreeNode right = Mirror(pRoot.right);

        pRoot.left = right;
        pRoot.right = left;

        return pRoot;
    }

    /*
    题目 4：判断是否为二叉搜索树
     */
    public boolean isValidBST (TreeNode root) {
        // 我自己的一个思路，是 中序遍历，把节点都装进一个 栈里面，最后再依次弹出比较大小
        Stack<TreeNode> stack = new Stack<>();
        inOrder(stack, root);

        if(stack.size() < 2){
            return true;
        }

        TreeNode node1 = stack.pop();

        while(!stack.isEmpty()){
            TreeNode node2 = stack.pop();
            if(node1.val < node2.val){
                return false;
            }else{
                node1 = node2;
            }
        }
        return true;
    }

    private void inOrder(Stack<TreeNode> stack, TreeNode root){
        if(root == null){
            return;
        }

        inOrder(stack, root.left);
        stack.push(root);
        inOrder(stack, root.right);
    }

    // 代码能否写得更加精练一点呢？
    

    //方法 2：递归：
    // 定义一个 pre
    int pre = Integer.MIN_VALUE;
    public boolean isValidBST1 (TreeNode root) {
        // 使用 递归
        if(root == null){
            return true;
        }

        // 中序遍历
        // 左子树返回的是 false 的话
        // 那么返回 false
        if(!isValidBST(root.left)){
            return false;
        }

        if(pre > root.val){
            return false;
        }

        pre = root.val;

        return isValidBST(root.right);

    }
}
